package week02

// 17. 电话号码的字母组合
// https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/


// 1、遍历所有分支
// 2、更新答案
// 3、递归
// 4、还原现场
// 5、退出条件
// ps：树形状，不需要判重

func letterCombinations(digits string) []string {
	if digits == "" {
		return []string{}
	}
	return dfs([]byte(digits), []byte{}, []string{}, 0)

}

func dfs(digits, temp []byte, ans []string, index int) []string {
	if len(digits) == index {
		return append(ans, string(temp))    // 类型转换本身就发生了内存copy，
	}

	list := m[digits[index]]
	for _, byt := range list {
		temp = append(temp, byt)
		ans = dfs(digits, temp, ans, index+1)
		temp = temp[:len(temp)-1]
	}
	return ans
}

var m = map[byte][]byte{
	'2': []byte{'a', 'b', 'c'},
	'3': []byte{'d', 'e', 'f'},
	'4': []byte{'g', 'h', 'i'},
	'5': []byte{'j', 'k', 'l'},
	'6': []byte{'m', 'n', 'o'},
	'7': []byte{'p', 'q', 'r', 's'},
	'8': []byte{'t', 'u', 'v'},
	'9': []byte{'w', 'x', 'y', 'z'},
}